package datastructure.sort;

public class InsertionSort extends AbstractArray {

	public InsertionSort(int max) {
		super(max);
	}

	@Override
	public void sort() {
		insertionSort();
	}

	/*
	 * based on marker and assume right side array of marker is unsorted.
	 */
	public void insertionSort() {
		int in, out;
		for (out = 1; out < nElems; out++) {
			int temp = a[out];
			in = out;
			while (in > 0 && a[in - 1] >= temp) {
				a[in] = a[in - 1];
				--in;
			}
			a[in] = temp;
		} // end for
	} // end insertionSort()

	// =================================
	// +++++++++++++++++++++++++++++++++
	// =================================
	public static void main(String[] args) {

		InsertionSort arr = new InsertionSort(maxSize);
		arr.insert(77);
		arr.insert(99);
		arr.insert(44);
		arr.insert(55);
		arr.insert(22);
		arr.insert(88);
		arr.insert(11);
		arr.insert(00);
		arr.insert(66);
		arr.insert(33);

		System.out.println("Input Array: ");
		arr.display();

		arr.sort();

		System.out.println("\nAfter InsertionSort : ");
		arr.display();
	} // end main()

}
